package Graph;

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collector;
import java.util.stream.Collectors;

public class FloydWarshall {
    //FloydWarshall 多源最短路径
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        v1.edges = List.of(new Edge(v3, -2)
        );
        v2.edges = List.of(new Edge(v1, 4),
                new Edge(v3, 3)
        );

        v3.edges = List.of(new Edge(v4, 2)
        );
        v4.edges = List.of(new Edge(v2, -1));

        List<Vertex> graph = List.of(v1, v2, v3, v4);
        floydwarshall(graph);
    }

    private static void floydwarshall(List<Vertex> graph) {
        int size = graph.size();
        int[][] dist = new int[size][size];
        //初始化
        for (int i = 0; i < size; i++) {
            Vertex v = graph.get(i);
            Map<Vertex, Integer> map = v.edges.stream().collect(Collectors.toMap(e -> e.linked, e -> e.weigth));
            for (int j = 0; j < size; j++) {
                Vertex u = graph.get(j);
                if (v == u) {
                    dist[i][j] = 0;
                } else {
                    Integer orDefault = map.getOrDefault(u, Integer.MAX_VALUE);
                    dist[i][j] = orDefault;
                }
            }
        }
        //看是否能借路到达
        for (int k = 0; k < size; k++) {
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }

                }
            }
        }
        print(dist);
    }

    public static void print(int[][] dist) {
        System.out.println("-----");
        for (int[] ints : dist) {
            for (int anInt : ints) {
                System.out.print(anInt != Integer.MAX_VALUE ? anInt + " " : "∞" + " ");
            }
            System.out.println();
        }
        System.out.println("-----");

    }
}
